package DynamicProgrammingPackage;

/**
 * @author Lzm
 * @version 1.0
 */
public class fib_ {
  public static void main(String[] args) {
    System.out.println(fib(4));
  }

  // 1. dp数组: dp[i]表示第i个斐波那契数dp[i]
  // 2. 递推公式: dp[i] = dp[i - 1] + dp[i - 2]
  // 3. 初始化: dp[0] = 0, dp[1] = 1; dp = new int[n + 1]
  // 4. 遍历顺序: 从前向后, 因为 第i个数依赖第i - 1个数和第i - 2个数, 所以要从前向后遍历
  public static int fib(int n) {
    if (n == 0){
      return 0;
    }
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    if (n == 0){
      return 0;
    }
    else if(n == 1){
      return 1;
    }
    for (int i = 2 ; i <= n ; i++){
      dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
  }
}
